Search for: All records

Abstract In this paper, we focus on constructing unique-decodable and list-decodable codes for the recently studied (t, e)-composite-asymmetric error-correcting codes ((t, e)-CAECCs). Let$$\mathcal {X}$$ $X$be an$$m \times n$$ $m\times n$binary matrix in which each row has Hamming weightw. If at mosttrows of$$\mathcal {X}$$ $X$contain errors, and in each erroneous row, there are at mosteoccurrences of$$1 \rightarrow 0$$ $1\to 0$errors, we say that a (t, e)-composite-asymmetric error occurs in$$\mathcal {X}$$ $X$. For general values ofm, n, w, t, ande, we propose new constructions of (t, e)-CAECCs with redundancy at most$$(t-1)\log (m) + O(1)$$ $(t-1)log\left(m\right)+O\left(1\right)$, whereO(1) is independent of the code lengthm. In particular, this yields a class of (2, e)-CAECCs that are optimal in terms of redundancy. Whenmis a prime power, the redundancy can be further reduced to$$(t-1)\log (m) - O(\log (m))$$ $(t-1)log\left(m\right)-O(log(m\left)\right)$. To further increase the code size, we introduce a combinatorial object called a weak$$B_e$$ $B_e$-set. When$$e = w$$ $e=w$, we present an efficient encoding and decoding method for our codes. Finally, we explore potential improvements by relaxing the requirement of unique decoding to list-decoding. We show that when the list size ist! or an exponential function oft, there exist list-decodable (t, e)-CAECCs with constant redundancy. When the list size is two, we construct list-decodable (3, 2)-CAECCs with redundancy$$\log (m) + O(1)$$ $log\left(m\right)+O\left(1\right)$. 

https://doi.org/10.1007/s10623-024-01481-z